package lcr;

import java.util.Deque;
import java.util.LinkedList;

public class Test0043 {
}

class CBTInserter {

    private Deque<TreeNode> deque= new LinkedList<>();
    private TreeNode root;

    public CBTInserter(TreeNode root) {
        deque.offer(root);
        while (deque.peek().left!=null&&deque.peek().right!=null){
            deque.offer(deque.peek().left);
            deque.offer(deque.peek().right);
            deque.poll();
        }
        if (deque.peek().left!=null) deque.offer(deque.peek().left);
        this.root = root;
    }

    public int insert(int v) {
        TreeNode peek = deque.peek();
        TreeNode node = new TreeNode(v);
        if (peek.left==null){
            peek.left = node;
        } else{
            peek.right = node;
            deque.poll();
        }
        deque.offer(node);
        return peek.val;
    }

    public TreeNode get_root() {
        return root;
    }
}
